题解[SCOI2009]最长距离

这题暴力建图再加个最短路就可以过。

对于一个点 $x$，我们给它和它相邻的点之间连一条有向边，若相邻的点为石头，则边权为 $1$，反之，则为 $0$。

然后大力枚举每一个点 $x$，对于每一个点都跑一遍 Dijskra 算法，这时候，我们就已经求出了点 $x$ 到其他所有点需要经过的石头的数量的最小值，然后再枚举终点更新答案即可，时间复杂度 $\Theta(n^4)$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#define get(x, y) ((x - 1) * n + y)
using namespace std;
const int N = 1e6 + 5;
typedef pair<int, int> PII;

char sq[35][35];
int dis[905];
int head[N], ver[N], net[N], edge[N], idx;
bool vis[905];

void add(int a, int b, int c)
{
    net[++idx] = head[a], ver[idx] = b, edge[idx] = c, head[a] = idx;
}

void Dij(int s, int d)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = d;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({d, s});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = net[i])
        {
            int v = ver[i];
            if (dis[v] > dis[u] + edge[i])
            {
                dis[v] = dis[u] + edge[i];
                q.push({dis[v], v});
            }
        }
    }
}

double get_dis(int x, int y, int xx, int yy)
{
    return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy)); 
}

int main()
{
    int n, m, t;
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++)
        scanf("%s", sq[i] + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i > 1)
                add(get(i, j), get(i - 1, j), sq[i - 1][j] == '1');
            if (i < n)
                add(get(i, j), get(i + 1, j), sq[i + 1][j] == '1');
            if (j > 1)
                add(get(i, j), get(i, j - 1), sq[i][j - 1] == '1');
            if (j < m)
                add(get(i, j), get(i, j + 1), sq[i][j + 1] == '1');
        }
    }
    double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            Dij(get(i, j), sq[i][j] == '1');
            for (int x = 1; x <= n; x++)
            {
                for (int y = 1; y <= m; y++)
                {
                    if (dis[get(x, y)] <= t)
                        ans = max(ans, get_dis(i, j, x, y));
                }
            }
        }
    }
    printf("%.6lf", ans);
    return 0;
}